#include <vector>
#include <string>
#include <stack>

using namespace std;

// 最长有效括号
// 给你一个只包含 '(' 和 ')' 的字符串
// 找出最长有效（格式正确且连续）括号子串的长度。
// 测试链接 : https://leetcode.cn/problems/longest-valid-parentheses/

// 动态规划的写法
// 时间复杂度 O(n)，n 是 s 字符串的长度
class Solution 
{
public:
    int longestValidParentheses(string s) 
    {
        int n = s.size();
        if(n == 0) return 0;

        // dp[0...n-1]
		// dp[i] : 子串必须以 i 位置的字符结尾的情况下，往左整体有效的最大长度
        vector<int> dp(n);
        int ans = 0;
        for(int i = 1; i < n; ++i)
        {
            if(s[i] == ')')
            {
                int p = i - dp[i - 1] - 1;
                if(p >= 0 && s[p] == '(')
                {
                    dp[i] = dp[i - 1] + 2 + (p - 1 >= 0 ? dp[p - 1] : 0);
                }
            }
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};


// 借助栈的写法
class Solution 
{
public:
    int longestValidParentheses(string s) 
    {
        int ret = 0, n = s.size();
        stack<int> st;
        // st.top() : 与当前右括号配对的左括号再前一个左括号的下标
        st.push(-1); 
        for(int i = 0; i < n; ++i)
        {
            if(s[i] == '(') st.push(i);
            else
            {
                st.pop(); // 弹出与该右括号配对的左括号
                if(st.empty()) st.push(i);
                else ret = max(ret, i - st.top()); 
            }
        }

        return ret;
    }
};

// 不借助栈，两次遍历的写法
class Solution 
{
public:
    int longestValidParentheses(string s) 
    {
        int left = 0, right = 0, n = s.size(), ret = 0;
        for(int i = 0; i < n; ++i)
        {
            if(s[i] == '(') ++left;
            else ++right;

            if(left == right) ret = max(ret, 2 * right);
            else if(right > left) left = right = 0;
        }

        left = right = 0;
        for(int i = n - 1; i >= 0; --i)
        {
            if(s[i] == '(') ++left;
            else ++right;

            if(left == right) ret = max(ret, 2 * left);
            else if(left > right) left = right = 0;
        }

        return ret;
    }
};